﻿#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//void getReshuffleCard(vector<int>& card, int n, int k)
//{
//
//    for (int count = 0; count < k; ++count)
//    {
//        vector<int> arr(card);
//        int end1 = n - 1;
//        int end2 = 2 * n - 1;
//
//        int cur = 0;
//        while (cur < arr.size())
//        {
//            card[cur++] = arr[end2--];
//            card[cur++] = arr[end1--];
//        }
//        reverse(card.begin(), card.end());
//    }
//}
//
//int main()
//{
//    int T = 0;
//    cin >> T;
//    for (int i = 0; i < T; ++i)
//    {
//        int n = 0;
//        int k = 0;
//        cin >> n >> k;
//        vector<int> card(2 * n);
//        for (auto& num : card)
//        {
//            cin >> num;
//        }
//
//        getReshuffleCard(card, n, k);
//
//        for (const auto& num : card)
//        {
//            cout << num << ' ';
//        }
//        cout << endl;
//    }
//
//    return 0;
//}

//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//const int PAGE_SIZE = 4;
//
//void up_order(vector<int>& song_list, int& cur)
//{
//    --cur;
//    if (cur < 0)
//    {
//        cur = song_list.size() - 1;
//    }
//
//}
//
//void down_order(vector<int>& song_list, int& cur)
//{
//    ++cur;
//    cur %= song_list.size();
//}
//
//int main()
//{
//    int song_num = 0;
//    string Command;
//
//    cin >> song_num;
//    vector<int> song_list(song_num);
//
//    for (int i = 0; i < song_num; ++i)
//    {
//        song_list[i] = i + 1;
//    }
//
//    cin >> Command;
//
//    int cur = 0;
//    for (const auto& com : Command)
//    {
//        switch (com)
//        {
//        case 'U':
//            up_order(song_list, cur);
//            break;
//        case 'D':
//            down_order(song_list, cur);
//            break;
//        default:
//            cout << com << endl;
//            break;
//        }
//    }
//
//    //找当前页
//    int page_down = cur;
//    int page_up = 0;
//
//    while (page_down < song_num && (page_down % PAGE_SIZE) != 0)
//    {
//        ++page_down;
//    }
//    page_up = page_down - PAGE_SIZE;
//    if (page_up < 0)
//    {
//        page_up = 0;
//    }
//
//    for (int i = page_up; i <= page_down; ++i)
//    {
//        cout << song_list[i] << ' ';
//    }
//    cout << endl << song_list[cur] << endl;
//
//    return 0;
//}
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct node
{
    char data[10];
    struct node* next;
}ListNode;
typedef ListNode* LinkList;//

//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1()
{
    char ch[100], ch1[10], c;
    int i = 0, j = 0;
    LinkList head = (LinkList)malloc(sizeof(ListNode)); //生成头结点
    ListNode* s, * r;
    r = head;
    r->next = NULL;
    printf("Input # to end  ");  //输入"#"代表输入结束
    printf("Please input Node_data:");
    scanf("%s", ch);           //输入各结点的字符串
    do
    {
        c = *(ch + i++);
        *(ch1 + j++) = c;
        if (c == ',')
        {
            s = (LinkList)malloc(sizeof(ListNode));
            for (j = 0; (j < 10) && *(ch1 + j) != ','; j++) *(s->data + j) = *(ch1 + j);
            *(s->data + j) = '\0';
            //为节点s的指针域赋值

            s->next = NULL;
            //将节点s连接在尾指针之后
            r->next = s;

            //修改尾指针
            r = s;
            j = 0;
        }
    } while (c != '#');
    return head;        //返回头指针
}


//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode* LocateNode(LinkList head, char* key)
{
    ListNode* p = head->next;
    int i = 1;
    while (p && strcmp(p->data, key) != 0)
    {
        //访问下一个节点p
        p = p->next;
        //计数器i记录当前节点的位序	
        i++;
    }
    if (!p)
    {
        printf("the location of the node is :%d\n", i);
        exit(0);
    }
    return p;    //若p=NULL则查找失败，否则p指向找到的值为key的结点
}

//===========打印链表中所有节点=======
void printlist(LinkList head)
{
    ListNode* p = head->next;       //从开始结点打印
    while (p)
    {
        //打印节点p中的数据
        printf("%s\t", p->data);

        //将节点p变为其后继节点
        p = p->next;
    }
    printf("\n");
}

//删除指定链表head中的值为key的节点
int DeleteNode(LinkList head, char* key)
{
    ListNode* p = head->next;
    ListNode* q = head;
    while (p && strcmp(p->data, key) != 0)
    {
        //将节点p后移
        p = p->next;

        //同时将节点q后移
        q = q->next;

    }
    if (p)    //找到p，则执行删除节点p 
    {
        //修改p的前驱q的指针域，让其值为p的后继
        q->next = p->next;

        //释放节点p所占据的存储空间
        free(p);
        return 1;
    }
    else
    {
        printf("P is not finded！\n");
        return 0;
    }

}
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
    ListNode* p = head, * r;
    while (p->next)
    {
        r = p->next;
        free(p);
        p = r;
    }
    free(p);
}

//在链表中第n个节点前插入新的节点，其数据为key
int insert_sq(LinkList head, int n, char* key)
{
    int in = 0, i = 0;
    ListNode* p = head, * s;
    while (p->next)  //查找第 n - 1 个节点，该节点为p
    {
        if (in++ < n - 1)
            p = p->next;
        else  //找到节点p时执行插入操作
        {
            //生成要插入的节点s
            s = (ListNode*)malloc(sizeof(ListNode));

            //为节点s的数据域赋值
            strcpy(s->data, key);

            //为节点s的指针域赋值
            s->next = p->next;

            //将节点s插入到节点p之后
            p->next = s;
            return 1;
        }
    }
    /* if (p->next == NULL && in == n - 1)
     {  s = (ListNode*)malloc(sizeof(ListNode));
     strcpy(s->data, key);
     s->next = p->next;
     p->next = s;
     return 1;
 }*/
    return -1;
}
//==========主函数 ==========
int main()
{
    LinkList h = NULL;
    ListNode* tx;
    char cmd;
    int i = 0;
    char temp[100];
    printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH\n");
    while (1)
    {
        cmd = getchar();
        switch (cmd)
        {
        case 'C':
        case 'c':
            h = CreatListR1();
            printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH\n");
            break;
        case 'I':
        case 'i':
            printf("please input the number to be inserted,end with '#'\n");
            scanf("%s", temp);
            printf("please input the position to be inserted\n");
            scanf("%d", &i);

            printf("%d\n", insert_sq(h, i, temp));
            printf("**********Sqlist inserted**********\n");
            printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSER,S=SEARCT\n");
            break;
        case 'S':
        case 's':
            printf("please input the number wanted\n");
            scanf("%s", temp);
            tx = LocateNode(h, temp);
            if (tx != NULL)  printf("the node found is:%s\n", tx->data);
            else printf("the node is not found!\n");
            printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARC\n");
            break;
        case 'D':
        case 'd':
            printf("please input the Node wanted\n");
            scanf("%s", temp);
            if (DeleteNode(h, temp))printf("The Node Deleted!\n");
            else printf("Node Deleted error!\n");
            printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARC\n");
            break;
        case 'P':
        case 'p':
            printlist(h);
            printf("X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARC\n");
            break;
        case 'X':
        case 'x':
            DeleteAll(h);
            return 1;
        default:break;
        }
    }
    return 0;
}